Methods for reliably broadcasting information in a distributed network of processors enable the fault-free components of that system to have consistent views of the global system state in the presence of faulty components. A reliable broadcast method guarantees (1) that a message broadcast is either accepted by all fault-free processors exactly once or by none of them (atomicity), (2) that a message broadcast by a fault-free sender is accepted correctly by all fault-free processors after a known time (termination), and (3) that all messages accepted by fault-free processors are accepted in the same order by all those processors (order). Such a method is an essential part of many protocols for distributed systems, e.g. updating replicated data.
Dolev and Strong, "Authenticated Methods for Byzantine Agreement", SIAM Journal of Computing, Vol. 12, No. 4, November 1983, describe a method for achieving atomic broadcast assuming a (logically) fully-connected network of processors. In order to tolerate F faults, their method runs for (F+1) phases and exchanges (N-1).sup.2 logical messages, where N is the number of processors in the network and the duration of a phase is the maximum network transmission delay.
Reference should also be made to Dolev et al, "A Method for Achieving Multiple Processor Agreement Optimized for No Faults", copending U.S. patent application Ser. No. 06/485,573, filed Apr. 13, 1983 now U.S. Pat. No. 4,569,015. They describe a method for atomic broadcast in a reliable (F+1) connected network of N processors with guaranteed early stopping in the absence of faults, and eventual stopping for F&lt;(N/2) faults.